Navigation aid systems for use inside buildings, and more generally in places inaccessible to communication via satellite, cannot currently use positioning or georeferencing systems such as GPS. Inside buildings, it must therefore be possible to use other types of navigation systems. In this case, one of the possible solutions is based on the use of an inertial navigation system.
An inertial navigation system is a navigation aid based on movement sensors (accelerometers) and rotation sensors (gyrometers) contained, for example, in an inertial navigation unit. The measurements obtained from these sensors are used to calculate the position, speed and orientation of the inertial navigation unit and, consequently, of the person carrying this system. Unlike other systems, notably systems for positioning via satellite (GPS), via Wi-Fi terminals, Bluetooth, etc., inertial navigation systems are completely autonomous in the sense that they do not depend on the transmission or reception of signals in relation to an external source. They are thus suitable for environments inaccessible to electromagnetic waves. However, these inertial navigation systems depend on the a priori knowledge of the position, speed and orientation of the inertial navigation unit (and therefore the carrier of the system) at the start of the navigation. This information can be supplied by the system operator or can be estimated at the start on the basis of other types of sensor (GPS, RFID, etc.). The position, speed and orientation of the inertial navigation unit are updated progressively on the basis of the measurements of the inertial sensors by suitable algorithms.
In its simplest implementation, a standard inertial navigation system comprises a computing unit and inertial sensors of the accelerometer and gyrometer type. In a general manner, the computing unit mainly comprises two modules: the integration module and the error estimation module. The first is dedicated to the calculation of the position, speed and orientation of the navigation unit through the integration of inertial signals. The second module is dedicated to the estimation of drift errors caused by inertial sensor shortcomings. This estimation is typically carried out using an indirect Kalman filter, the inputs of which depend on additional information sources such as navigable maps, compasses, GPS, etc. The success of these systems depends largely on the accuracy of inertial sensors, the available additional information sources and the manner of making use of the latter.
Given that most navigation systems give the position and orientation of the carrier in relation to a digitized navigation map describing the navigable space, this digital map represents the most readily accessible additional information source for correcting drift errors. This results in methods for fusing inertial data and cartographic data, aiming to increase the accuracy of the inertial navigation systems. Consequently, a problem to be resolved lies in obtaining a method for fusing cartographic data in order to correct the drift errors of an inertial navigation system meeting the following requirements:                Having a low complexity of the method in order to allow a better response to the real-time constraints in hardware and software architectures having a limited computing capacity;        Being suitable for existing navigation maps in navigation and guidance systems commonly used for route calculations;        Being independent of the change model of the navigating object.        
In particular, it must be noted that, for the navigation device to be portable, i.e. light and small, it must be implemented in dedicated hardware architectures commonly known as “on-board systems”. In a general manner, these systems have constraints in terms of computing power, memory space, energy consumption, etc. Consequently, the location methods taking account of cartographic data must take account of these constraints.
Current solutions do not allow these requirements to be met. In particular, methods can be found in the prior art based on particle filters, known to have a high computing power requirement, or methods based on direct Kalman filters, requiring change models of the navigating object.
As far as solutions based on particle filters are concerned, the document by B. Krach and P. Roberston, Cascaded estimation architecture for integration of foot-mounted inertial sensors, Proc. IEEE/ION Position, Location and Navigation Symposium, 2008, pp. 112-119, proposes an inertial navigation system for pedestrians using the technology of MEMS-based miniature inertial navigation units. The solution uses the standard navigation system, previously described, and adds a second data processing module, the inputs of which are the outputs of the standard navigation system, i.e. the estimated position, speed and orientation, and also the cartographic data. The fusion of these inputs is carried out via a particle filter. For its part, the particle filter brings the cartographic data into play via a change model associated with the particles. The principle of this change is as follows: each particle, representing a hypothetical position and orientation of the carrier, for example the pedestrian, changes to a different position provided that there is no obstacle between these two positions. The geographical location of the obstacles, representing walls, for example, is known in advance thanks to the digital map of the locations.
A different document by Widyawan, M. Klepal, and S. Beauregard, A backtracking particle filter for fusing building plans with pdr displacement estimates, Proc. 5th Workshop on Positioning, Navigation and Communication WPNC 2008, 27-27 Mar. 2008, pp. 207-212, presents a system similar to that of the preceding document for the fusion of inertial and cartographic data. The only difference is that, according to this second document, a conventional error estimation algorithm is not implemented, i.e. the algorithm based on a Kalman filter, but the API (Application Programming Interface) supplied by the manufacturer of the inertial navigation unit is used directly in order to obtain an estimation of the orientation of the inertial navigation unit. This API uses a Kalman filter to estimate the orientation of the inertial navigation unit on the basis of the measurements of the accelerometers, gyrometers and magnetometers. On the basis of this estimation, the authors of the document apply conventional integration formulae to the measurements of the accelerometers in order to obtain the position and speed of the pedestrian carrying the navigation system.
The solutions proposed in these documents nevertheless have a plurality of disadvantages:                It is well known that particle filters make intensive use of computing time, which makes their real-time implementation possible only on very powerful and barely portable platforms;        More particularly, the approaches proposed by the two preceding documents need to know if a wall has been passed through between two consecutive steps of the carrier. This presupposes a real-time test to determine if the straight-line segment described by the two positions, of the two steps, intersects with a straight-line segment representing a wall. The test may prove to be lengthy and time-consuming if the number of walls is large, in the case, for example, of a building with a large number of rooms. This test is all the more time-consuming bearing in mind that it must be carried out for each of the hypotheses, particles, of which the number must be large enough in order to obtain an accurate estimation of the position of the pedestrian;        These approaches require a digital map of the locations, designed specifically for this purpose. In other words, these approaches do not gain any benefit from the conventional navigation maps which are often used in conventional navigation systems (GPS, tomtom, etc.). Consequently, a navigation system which uses the algorithms proposed in the preceding documents requires a second specific navigation map in order to be able to calculate, in addition to the position and orientation, the route to be followed by the pedestrian.        
As far as the use of the algorithms based on Kalman filters is concerned, a plurality of solutions have been proposed. In particular, various methods for integrating cartographic data into Kalman filtering have been proposed for land and air vehicle tracking applications. All of these techniques apply to the direct Kalman filter, where the change model of the vehicle is available. Given that, in the context of pedestrian inertial navigation, the indirect Kalman filter is used, because the change model of the pedestrian is not known, the algorithms based on an implementation of the direct Kalman filter do not apply.
In a general manner, the indirect Kalman filter is the tool most often used in an error estimation module. This is due to the fact that it can operate in real time at a very high rate, and due to the fact that it is independent from the change model of the inertial navigation unit, i.e. the dynamic model describing the changes in the position, speed and orientation of the navigation unit over time. In fact, the indirect Kalman filter follows the changes in the errors of the integration module and not the changes in the position, speed and orientation of the navigation unit. Consequently, the indirect Kalman filter is independent from this change model. This offers an advantage, for example for locating a pedestrian, since, at the current time, it is not known how to model the movement of the navigation unit when it is attached to the pedestrian, ideally placed on the foot of the latter. Nevertheless, this independence also results in the impossibility of directly considering the movement constraints, introduced by the cartographic data, in the indirect Kalman filter.
One way to get round this obstacle to the fusion of inertial data and cartographic data, in the context of the indirect Kalman filter, is to use the technique known as “map-matching”. This technique consists in taking the output of the standard navigation system, i.e. the position, and projecting it onto the digitized navigation map in order to obtain a “corrected” position.
The document by Daniela Büchel and Pierre-Yves Gilliéron, Navigation pédestre à l'intérieur des bâtiments [“Pedestrian navigation inside buildings”], Géomatique Suisse 11/2004 (2004), pages 664-668, proposes two map-matching techniques suitable for pedestrian navigation. The first of these techniques, referred to as point-to-point map-matching, re-adjusts the estimated position in relation to the nearest node of the map. These nodes represent characteristic points such as doors, junctions, or floor connectors. The second technique, referred to as point-to-edge map-matching, determines the nearest edge of the estimated position. The edges represent a route portion modeled by a straight line between two nodes.
One disadvantage of these map-matching techniques is notably that they do not contribute to the estimation of errors of the integration module. In particular, apart from the position which is possibly re-adjusted, orientation and speed errors are not corrected. This lack of corrections results in the medium term in an increase in the errors, ultimately having an adverse effect on the estimated position.